/********************************************************************************
 * @Author: Zhenzhou Liu
 * @Date: 2024-12-28
 * @Description: Cg图论练习之所有点对最短距离（Floyd）
 *******************************************************************************/
#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> floyd(const vector<vector<int>> & adj) {
    int n = adj.size();
    vector<vector<int>> dist(n, vector<int>(n));
    vector<vector<int>> record(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            record[i][j] = -1;
            if (i != j) {
                dist[i][j] = adj[i][j];
            } else {
                dist[i][j] = 0;
            }
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    record[i][j] = k;
                }
            }
        }
    }

    return dist;
}

int main(int argc, char *argv[]) {
    int n, q;
    cin >> n >> q;
    vector<vector<int> > adj(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> adj[i][j];
        }
    }
    vector<vector<int>> query(q, vector<int>(2));
    for (int i = 0; i < q; ++i) {
        cin >> query[i][0] >> query[i][1];
    }

    vector<vector<int>> dist = floyd(adj);
    for (int i = 0; i < q; ++i)
        cout << dist[query[i][0] - 1][query[i][1] - 1] << endl;
    return 0;
}

/* Test Case1
3 1
0 1 4
1 0 2
3 1 0
1 3
*/

